class Solution {
    public:
        int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
            int nums_of_job = profit.size();
            vector<vector<vector<int>>> dp(nums_of_job+1,vector<vector<int>>(minProfit+1,vector<int>(n+1)));
            for(int i = 0 ; i < n + 1 ; i++) dp[0][0][i] = 1; //只要有员工，那么就能什么都不选
            for(int i = 1 ; i < nums_of_job+1 ; i++){
                for(int j = 0 ; j < minProfit+1 ; j++){
                    for(int p = 0 ; p < n+1 ; p++){
                        dp[i][j][p] = p>=group[i-1]? (dp[i-1][j][p]+dp[i-1][max(0,j-profit[i-1])][p-group[i-1]])%(1000000007) : dp[i-1][j][p]%(1000000007); //profit[i-1]可以大于j，这时我们只选i-1位置的值就可符合利润要求，那么我们可以挑选利润为0的位置
                    }
                }
            }
            return dp[nums_of_job][minProfit][n];
        }
    };